package leetcode_core.leetcode_1;

/**
 * Definition for a binary tree node.
 * public class leetocde_1.TreeNode {
 *     int val;
 *     leetocde_1.TreeNode left;
 *     leetocde_1.TreeNode right;
 *     leetocde_1.TreeNode() {}
 *     leetocde_1.TreeNode(int val) { this.val = val; }
 *     leetocde_1.TreeNode(int val, leetocde_1.TreeNode left, leetocde_1.TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class IsValidBST {
    public boolean isValidBST(TreeNode root) {
        return this.isValidBST(root,null,null);
    }

    /**
     * max和min相当于给子树上的所有节点添加了一个min和max的边界,约束root的左子树节点值不超过root的值
     * 右子树的节点值不小于root的值,也就符合BST定义
     * @param root
     * @param min
     * @param max
     * @return
     */
    private boolean isValidBST(TreeNode root,TreeNode min,TreeNode max){//保证root.val在(min,max)之间
        //一行一行代码来解释
        if(root == null){//如果检索到空节点,那么就证明这条路径上的所有节点都是符合BST定义的,我们认为这一次的搜索是合法的
            return true;
        }
        //min节点代表一个下界,也就是当前检索的节点不得小于等于这个节点的值
        if(min!= null && root.val<= min.val){
            return false;
        }
        //max节点代表一个上界,也就是当前检索的节点不得大于等于这个节点的值
        if(max!=null && root.val >= max.val){
            return false;
        }
        //这一句非常关键:
        //1.规定了遍历方向,从root开始,检索root.left和root.right
        //2.当检索root.left的时候,也就是检查它的左子树,那么对于这个节点而言和它的左子树而言,其上边的所有的值都不能够超过root.val,因此max设置为root
        //  至于min的话,对于左子树而言,左子树的最小值是否有要求呢?首先它是root的左子树,root要保证它的值不会违反整棵树都是BST这个原则,所以限制root的(l,r)都会继承下去
        //3.当检索root.right的时候,也就是检查它的右子树,那么对于这个节点而言和它的右子树而言,其上边的所有的值都不能够低于root.val,因此min设置为root
        //  至于max同理,需要继承,因为要求整棵树都得是合理的BST
        return isValidBST(root.left,min,root) && isValidBST(root.right,root,max);
    }




}
